/*
剑指 Offer II 010. 和为 k 的子数组
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

 

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2 :

输入:nums = [1,2,3], k = 3
输出: 2
 

提示:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

 

注意：本题与主站 560 题相同： https://leetcode-cn.com/problems/subarray-sum-equals-k/
*/

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // n ^ 2 solution
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int result = 0;

        for(int start = 0;start < n; ++start)
        {
            int sum = 0;
            for(int end = start; end < n; ++end)
            {
                sum += nums[end];
                if(sum == k)
                    ++result;
            }
        }

        return result;
    }

    // n ^ 2 solution
    int subarraySum2(vector<int>& nums, int k)
    {
        int n = nums.size();
        vector<int> sums(n+1);
        int result = 0;
        for (int i = 1;i <= n; ++i)
        {
            sums[i] = sums[i - 1] + nums[i-1];
        }

        for(int start = 0;start < n; ++start)
        {
            for(int end = start + 1; end <= n; ++end)
            {
                if(sums[end] - sums[start] == k)
                {
                    ++result;
                }
            }
        }

        return result;
    }

    /*
    [i...j]组成的和可以看成[0...j-1]的和与[0...i]的和之差，如果分别用J,I来表示，即找到所有的J-I=target
    这里可以巧妙地采用hashmap数据结构，hashmap[sum]表示这个和sum在遍历的过程中出现的次数
    hashmap[5]=2 表示存在两种前缀和[0...i_1]和[0...i_2]和都等于5
    */
    int subarraySum3(vector<int>& nums, int k)
    {
        int n = nums.size();
        unordered_map<int,int> prefixSum;
        prefixSum[0] = 1;
        int result = 0;
        int sum = 0;
        for (int i = 0; i < n; ++i)
        {
            sum += nums[i];
            //prefixSum[j] - prefixSum[i] == k
            if(prefixSum.find(sum - k) != prefixSum.end())
            {
                result += prefixSum[sum-k];
            }

            //prefixSum[sum] = 1 or add 1 to original value
            prefixSum[sum] = prefixSum[sum] + 1;
        }
        
        return result;
    }
};